package _interview150;

/**
 * 427. 建立四叉树
 */
public class No427 {
    private int[][] grid;

    public Node construct(int[][] grid) {
        this.grid = grid;
        return dfs(0, 0, grid.length, grid[0].length);
    }

    private Node dfs(int row, int column, int rowLen, int columnLen) {
        int standVal = grid[row][column];
        boolean isSame = true;
        label:
        for (int i = row; i < rowLen; i++) {
            for (int j = column; j < columnLen; j++) {
                if (grid[i][j] != standVal) {
                    isSame = false;
                    break label;
                }
            }
        }
        int rowMid = (row + rowLen) / 2, columnMid = (column + columnLen) / 2;
        return isSame ? new Node(standVal == 1, true) : new Node(false, false,
                dfs(row, column, rowMid, columnMid),
                dfs(row, columnMid, rowMid, columnLen),
                dfs(rowMid, column, rowLen, columnMid),
                dfs(rowMid, columnMid, rowLen, columnLen));
    }

    class Node {
        public boolean val;
        public boolean isLeaf;
        public Node topLeft;
        public Node topRight;
        public Node bottomLeft;
        public Node bottomRight;


        public Node() {
            this.val = false;
            this.isLeaf = false;
            this.topLeft = null;
            this.topRight = null;
            this.bottomLeft = null;
            this.bottomRight = null;
        }

        public Node(boolean val, boolean isLeaf) {
            this.val = val;
            this.isLeaf = isLeaf;
            this.topLeft = null;
            this.topRight = null;
            this.bottomLeft = null;
            this.bottomRight = null;
        }

        public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
            this.val = val;
            this.isLeaf = isLeaf;
            this.topLeft = topLeft;
            this.topRight = topRight;
            this.bottomLeft = bottomLeft;
            this.bottomRight = bottomRight;
        }
    }
}
